﻿#pragma once
#pragma once

#include <vector>
#include <algorithm>
#include <iostream>
#include <ctime>
#include <windows.h>
using namespace std;

/**
二维平面上有 NN 条直线，形式为 y = kx + b，其中 k、b为整数 且 k > 0。所有直线以 [k,b] 的形式存于二维数组 lines 中，不存在重合的两条直线。两两直线之间可能存在一个交点，最多会有 C_N^2C
N
2
​
  个交点。我们用一个平行于坐标轴的矩形覆盖所有的交点，请问这个矩形最小面积是多少。若直线之间无交点、仅有一个交点或所有交点均在同一条平行坐标轴的直线上，则返回0。

注意：返回结果是浮点数，与标准答案 绝对误差或相对误差 在 10^-4 以内的结果都被视为正确结果

示例 1：

输入：lines = [[2,3],[3,0],[4,1]]

输出：48.00000

解释：三条直线的三个交点为 (3, 9) (1, 5) 和 (-1, -3)。最小覆盖矩形左下角为 (-1, -3) 右上角为 (3,9)，面积为 48

示例 2：

输入：lines = [[1,1],[2,3]]

输出：0.00000

解释：仅有一个交点 (-2，-1）

限制：

1 <= lines.length <= 10^5 且 lines[i].length == 2
1 <= lines[0] <= 10000
-10000 <= lines[1] <= 10000
与标准答案绝对误差或相对误差在 10^-4 以内的结果都被视为正确结果
**/
const int T = 50;
const double inf = 1e9;

class MiniRectAreaLCP37 {
public:
    /// <summary>
    /// k1x + b1 = k2x + b2
    /// (k1 - k2)x = b2 - b1
    /// x = (b2 - b1) / (k1 - k2)
    /// 
    /// y = k1 * (b2 - b1) / (k1 - k2) + b1
    /// y = (k1*b2 - k1*b1 + k1*b1 - k2*b1) / (k1 - k2)
    /// y = (k1*b2 - k2*b1) / (k1 - k2)
    /// 
    /// </summary>
    /// <param name="lines"></param>
    /// <returns></returns>
    double minRecSize(vector<vector<int>>& lines)
    {
        clock_t start = clock();
        double area = 0;
        double xMin = 0;
        double xMax = 0;
        double yMin = 0;
        double yMax = 0;
        int flagXMin = 0, flagXMax = 0, flagYMin = 0, flagYMax = 0;

        for (int idx1 = 0; idx1 != lines.size(); idx1++)
        {
            int k1 = lines[idx1][0];
            int b1 = lines[idx1][1];
            for (int idx2 = idx1 + 1; idx2 != lines.size(); idx2++)
            {
                int k2 = lines[idx2][0];
                int b2 = lines[idx2][1];

                if (k1 - k2 == 0)
                {
                    continue;
                }

                double x = double(b2 - b1) / double(k1 - k2);
                double y = double(k1 * b2 - k2 * b1) / double(k1 - k2);

                if (flagXMin == 1)
                {
                    if (xMin > x) {
                        xMin = x;
                    }

                    if (yMin > y) {
                        yMin = y;
                    }

                    if (xMax < x) {
                        xMax = x;
                    }

                    if (yMax < y) {
                        yMax = y;
                    }

                    //xMin = (xMin > x) ? x : xMin;
                    //yMin = (yMin > y) ? y : yMin;
                    //xMax = (xMax < x) ? x : xMax;
                    //yMax = (yMax < y) ? y : yMax; 
                }
                else
                {
                    flagXMin = 1;
                    xMin = x;
                    flagYMin = 1;
                    yMin = y;
                    flagXMax = 1;
                    xMax = x;
                    flagYMax = 1;
                    yMax = y;
                }
            }
        }
                
        area = (xMax - xMin) * (yMax - yMin);

        //Sleep(1000);

        clock_t end = clock();
        double programTimes = ((double)end - start) / CLOCKS_PER_SEC;
        cout << "programTimes: " << programTimes << std::endl;

        return area;
    }


    double minRecSize_1(vector<vector<int>>& lines)
    {
        int n = lines.size();
        if (n == 1)
            return 0.0;

        double rl = -inf, rr = inf;
        int t = T;
        sort(lines.begin(), lines.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
        });
        while (t--) {
            double mid = (rl + rr) * 0.5;
            bool conflict = false;
            for (int i = 0; i < n - 1; ++i) {
                double a = (double)lines[i][0] * mid + lines[i][1];
                double b = (double)lines[i + 1][0] * mid + lines[i + 1][1];
                if (a - b > 1e-8) {
                    conflict = true;
                    break;
                }
            }
            if (conflict)
                rl = mid;
            else
                rr = mid;
        }

        t = T;
        double ll = -inf, lr = inf;
        sort(lines.begin(), lines.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
            });
        while (t--) {
            double mid = (ll + lr) * 0.5;
            bool conflict = false;
            for (int i = 0; i < n - 1; ++i) {
                double a = (double)lines[i][0] * mid + lines[i][1];
                double b = (double)lines[i + 1][0] * mid + lines[i + 1][1];
                if (a - b > 1e-8) {
                    conflict = true;
                    break;
                }
            }
            if (conflict)
                lr = mid;
            else
                ll = mid;
        }

        t = T;
        double ul = -inf, ur = inf;
        sort(lines.begin(), lines.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] > b[0] || (a[0] == b[0] && a[1] > b[1]);
            });
        while (t--) {
            double mid = (ul + ur) * 0.5;
            bool conflict = false;
            for (int i = 0; i < n - 1; ++i) {
                double a = (mid - lines[i][1]) / lines[i][0];
                double b = (mid - lines[i + 1][1]) / lines[i + 1][0];
                if (a - b > 1e-8) {
                    conflict = true;
                    break;
                }
            }
            if (conflict)
                ul = mid;
            else
                ur = mid;
        }

        t = T;
        double dl = -inf, dr = inf;
        sort(lines.begin(), lines.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
            });
        while (t--) {
            double mid = (dl + dr) * 0.5;
            bool conflict = false;
            for (int i = 0; i < n - 1; ++i) {
                double a = (mid - lines[i][1]) / lines[i][0];
                double b = (mid - lines[i + 1][1]) / lines[i + 1][0];
                if (a - b > 1e-8) {
                    conflict = true;
                    break;
                }
            }
            if (conflict)
                dr = mid;
            else
                dl = mid;
        }

        if (ll - rr > 1e-8)
            return 0.0;

        return (rr - ll) * (ur - dl);
    }


    void test()
    {
        //vector<vector<int>> test1;
        //test1.push_back({1, 1});
        //test1.push_back({ 2, 3 });
        //double area1 = minRecSize(test1);
        //cout << "area1: " << area1 << std::endl;

        //vector<vector<int>> test2;
        //test2.push_back({ 3, 9 });
        //test2.push_back({ 1, 5 });
        //test2.push_back({ -1, -3 });
        //double area2 = minRecSize(test2);
        //cout << "area2: " << area2 << std::endl;

        //
        //vector<vector<int>> test3;
        //test3.push_back({ 2, 3 });
        //test3.push_back({ 3, 0 });
        //test3.push_back({ 4, 1 });
        //double area3 = minRecSize(test3);
        //cout << "area3: " << area3 << std::endl;

        ////[[5, 3], [3, -3], [5, 1], [5, -5], [5, -2]]
        //vector<vector<int>> test4;
        //test4.push_back({ 5, 3 });
        //test4.push_back({ 3, -3 });
        //test4.push_back({ 5, 1 });
        //test4.push_back({ 5, -5 });
        //test4.push_back({ 5, -2 });
        //double area4 = minRecSize(test4);
        //cout << "area4: " << area4 << std::endl;


        //[[2,0],[4,-3],[2,4],[1,-2],[1,-1]]
        vector<vector<int>> test5;
        test5.push_back({ 2, 0 });
        test5.push_back({ 4, -3 });
        test5.push_back({ 2, 4 });
        test5.push_back({ 1,-2 });
        test5.push_back({ 1,-1 });
        double area5 = minRecSize_1(test5);
        cout << "area5: " << area5 << std::endl;
    }
};
